/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        //解题思路为构造两个新链表一个储存小于x的一个储存大于等于x的节点，最后结合两个节点即可
        ListNode* lowlist = new ListNode(0);//储存小于x的节点
        ListNode* highlist = new ListNode(0);//储存大于x的头节点
        if(head == nullptr)
        {
            return  nullptr;
        }    
        ListNode* cur = head;
        ListNode* cur1 = lowlist;
        ListNode* cur2 = highlist;
        while(cur!=nullptr)
        {
            if(cur->val<x)
            {
                cur1->next = cur;
                cur1 = cur1->next;
            }
            else
            {
                cur2->next = cur;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        cur2->next = nullptr;
        cur1->next = highlist->next;
        ListNode* tmp = lowlist->next;
        return tmp;
    }
};